// bzoj3122
// 题意：给定一个页数的递推式子 Xi+1 == (a*Xi + b) (mod p)，给定X1, a, b, p，
//       问最少第几天到制定页数t。到不了输出-1.
//
// 题解：将式子推一下，写成通项。然后上baby step giant step就行。
//       注意各种细节啊。
//       如果X1 == t，那么就是1天;
//       如果 a == 0, 那么如果b == t就是2天，否则-1;
//       如果 a == 1, 那么如果b == 0就是-1, 否则就是一个umsole;
//       其余就是bsgs了。
//       另外get到一个hash不用初始化写法，弄个timestamp就好，每次只需要timestamp++初始化。
//
// 统计：4040ms，2h, 5wa
// run: $exec < bfdiff.in
#include <iostream>
#include <cstring>
#include <cmath>

typedef long long v_type;
long long p, a, b, x1, t;

namespace hash
{
	int const maxlen = 7679977;
	int hashed[maxlen];
	v_type key[maxlen];
	int value[maxlen];
	int timestamp = 1;

	void init() { timestamp++; }

	void insert(v_type k, int v)
	{
		int i = k % maxlen;
		for (; hashed[i] == timestamp && key[i] != k; i = (i + 1) % maxlen);
		if (hashed[i] != timestamp) { hashed[i] = timestamp; key[i] = k; value[i] = v; }
	}

	int find(v_type k)
	{
		v_type i = k % maxlen;
		for (; hashed[i] == timestamp && key[i] != k; i = (i + 1) % maxlen);
		if (hashed[i] != timestamp) return -1;
		return value[i];
	}
};

void extended_gcd(v_type a, v_type b, v_type & d, v_type & x, v_type & y)
{
	if (!b) { d = a; x = 1; y = 0; }
	else {
		extended_gcd(b, a % b, d, y, x);
		y -= x * (a/b);
	}
}

v_type inverse(v_type t, v_type p)
{
	v_type x, y, d;
	extended_gcd(t, p, d, x, y);
	return (x % p + p) % p;
}

v_type umsole(v_type a, v_type b, v_type p)
{
	v_type x, y, b0;
	extended_gcd(a, p, b0, x, y);
	v_type m = p / b0;
	return ((x * (b / b0)) % m + m) % m;
}

v_type bsgs(v_type a, v_type b, v_type p)
{
	v_type m = std::ceil(std::sqrt((double)(p-1)));
	hash::init();
	v_type d = 1;
	for (int i = 0; i < m; i++) {
		hash::insert(d, i);
		d = (d * a) % p;
	}

	v_type di = 1;
	for (int i = 0; i < m; i++) {
		v_type x = umsole(di, b, p);
		int tmp = hash::find(x);
		if (tmp != -1) return i * m + tmp;
		di = (di * d) % p;
	}
	return -1;
}

int main()
{
	int T;
	std::cin >> T;
	while (T--) {
		std::cin >> p >> a >> b >> x1 >> t;
		if (x1 == t) { std::cout << "1\n"; continue; }
		if (!a) { std::cout << (b == t ? 2 : -1) << '\n'; continue; }
		if (a == 1) {
			if (!b) { std::cout << "-1\n"; continue; }
			v_type tb = ((t - x1) % p + p) % p;
			v_type ans = (tb * inverse(b, p)) % p;
			std::cout << ans + 1 << '\n';
			continue;
		}
		v_type tc = b + (a - 1) * x1;
		tc = (tc % p + p) % p;
		v_type tb = t * (a - 1) + b;
		tb = (tb % p + p) % p;
		tb = (tb * inverse(tc, p)) % p;
		v_type tmp = bsgs(a, tb, p);
		if (tmp != -1) tmp++;
		std::cout << tmp << '\n';
	}
}

